Programmable Logic Devices (PLDs) are widely used to implement logic functions for controlling electronic devices. A mask-programmable logic device is programmed by a manufacturer through the process of fabricating the device. In contrast, a field-programmable logic device is distributed by a manufacturer in an unprogrammed state. The purchaser of the device subsequently programs it in the "field" to execute a desired function. The present invention relates to field programmable logic devices (FPLDs). Field Programmable Gate Arrays (FPGAs) are one form of FPLDs.
The primary benefit of FPLDs is that user-programmability allows for rapid and inexpensive prototype development. Another important benefit associated with FPLDs is that they may be re-programmed to implement different designs.
Specific designs to be implemented within a given architecture are developed with Electronic Design Automation (EDA) techniques, also referred to as Computer Aided Design (CAD) techniques. EDA tools include logic synthesizers, physical design tools, and timing verifiers. Logic synthesizers convert a high-level description of a circuit into a netlist which describes circuit components and the connections between the components. Given a netlist, physical design tools determine physical locations of the components and the wire segments required for realizing the connections between the components. This step of the design process is generally computationally expensive. Consequently, refining this process is an ongoing matter.
Timing verifiers analyze the timing performance of the circuit described in the netlist. Based upon the timing performance of the circuit, an engineer may modify the netlist to improve the performance of the circuit.
It is desirable to completely automate the implementation of a given circuit into an FPLD architecture. For this to occur, it is important to design the FPLD architecture to insure that the EDA tools can accurately estimate the timing performance and also be able to place and route a given circuit design with ease. The FPLD architecture should have the foregoing features without eliminating the ability to implement complex circuits.
Look-Up Tables (LUTs) are generally used in FPGAs. A LUT is a digital device that provides an output value for a given set of input values. The output value is stored at a memory location which is addressed by the input values.
LUT-based FPGAs utilize a sequence of LUTs to form a multi-level structure. In such a device, the output from a first LUT is combined with new input values at a second LUT to yield a new output value. The second LUT may be viewed as a second logic level. Likewise, the output value from the second LUT may be subsequently combined with additional input values at a third LUT. In such a device, there are three logic levels with a LUT at each logic level.
There are a number of problems associated with traditional LUT-based FPGAs. As described in the preceding paragraph, these devices have a sequential structure in which the LUTs are distributed over the silicon die which implements the logic. This approach can be spatially expensive. Another problem relates to routing the connections between the various LUTs. The connections between the LUTs may introduce unpredictable and undesirable signal propagation delays. The propagation delays may require re-placement and re-routing of the circuit until all timing constraints are met. In some circumstances, it may be impossible to place and route a given circuit design on an FPGA to satisfy reasonable timing constraints.